import std.stdio;
 

   /***********************************************************************
    * Devuelve true si la ubicacion de la reina en vector[colActual] no puede ser comida
    * por las otras reinas desde el vector[0] hasta vector[colActual-1]
    ***********************************************************************/
    bool isConsistent(int[] vector, int colActual) {
        for (int i = 0; i < colActual; i++) {
            if (vector[i] == vector[colActual])             return false;   // same column
            if ((vector[i] - vector[colActual]) == (colActual - i)) return false;   // same major diagonal
            if ((vector[colActual] - vector[i]) == (colActual - i)) return false;   // same minor diagonal
        }
        return true;
    }

   /***********************************************************************
    * Imprime el tablero con las reinas ya ubicadas
    ***********************************************************************/
    void printQueens(int[] vector) {
        int N = vector.length;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (vector[i] == j) { writef("Q "); }
                else           { writef("* "); }
            }
            writefln();
        }  
        writefln();
    }


   /***********************************************************************
    *  Prueba todas las permutaciones usando backtracking
    ***********************************************************************/
    void enumerate(int n) {
        int[] a = new int[n];
        enumerate(a, 0);
    }

    void enumerate(int[] vector, int n) {
        int longitud = vector.length;
        if (n == longitud) printQueens(vector);
        else {
            for (int i = 0; i < longitud; i++) {
                vector[n] = i;
                if (isConsistent(vector, n)) { 
					enumerate(vector, n+1); 
				}
            }
        }
    }  


    void main(char[][] args) {
		int n = 4;
		enumerate(n);
    }
